1. Field of the Invention
This invention relates to computer architecture, and more particularly, to a network-connected apparatus that allows multiple hosts to share a collection of memory sectors, in which the memory sectors are used to store compressed data. The apparatus will hereinafter be referred to as a “direct addressed Shared Compressed Memory System” (SCMS).
The invention includes methods for translating real addresses generated by the hosts into real addresses as managed by the SCMS, which are then translated into physical addresses by the compressed-memory management system; methods for ensuring memory content protection; mechanisms for sharing the content of memory among different hosts; methods for distributing a contiguous portion of the real address space of a host across multiple SCMSes; and methods for ensuring that each host can be guaranteed a certain number of memory sectors.
2. Description of the Related Art
An emerging development in computer organization is the use of data compression in a computer system's main memory. Real memory, namely, the set of processor addresses that correspond to data stored in memory, is typically divided into a number of pairwise disjoint segments corresponding to a fixed number of contiguous processor addresses. By pairwise disjoint, it is meant that each real address belongs to one and only one such segments. These segments are referred to as memory lines. Memory lines are the unit of compression. A memory line stored in the compressed memory is compressed and stored in a variable number of memory locations, which depends on how well its content compresses. International Business Machines (IBM) Corporation has several patents related to computer systems where the contents of main memory are compressed. Examples of such systems are disclosed in U.S. Pat. No. 5,729,228 entitled “Parallel compression and decompression using a cooperative dictionary” issued to Franaszek et al. on Mar. 17, 1998; U.S. Pat. No. 5,761,536 entitled “System and method for reducing memory fragmentation by assigning remainders to share memory blocks on a best fit basis” issued to Franaszek on Jun. 2, 1998; and U.S. Pat. No. 5,864,859 entitled “System and method of compression and decompression using store addressing” issued to Franaszek on Jan. 26, 1999.
FIG. 1 depicts an exemplary system having such data compression features. In FIG. 1, a central processing unit (CPU) 102 reads data to and writes data from one or more caches 104. Cache misses and stores result in reads from and writes to a compressed main memory 110 by means of a compression controller 106. The compressed main memory 110 is divided into two parts: a data portion 108 and a directory 107 (also known as a compression translation table CTT). The data portion 108 is divided into pairwise disjoint sectors, i.e., fixed-size intervals of physical memory locations. For example, a sector might consist of 256 physical bytes having contiguous physical addresses. The content of a compressed memory line is stored in the minimum possible number of physical sectors. The physical sectors containing a compressed line need not have contiguous physical addresses, and can be located anywhere within the data portion 108 of the compressed main memory 110. The translation between the real address of a byte and the address of the physical sector containing it is performed via the directory or CTT 107.
FIG. 2 contains further details to better understand the operation of the compressed memory 210. A processor cache 240 contains uncompressed cache lines 241 and a cache directory 242, which stores the real address of each cache line. For the purpose of illustration, it will be assumed that a cache line has the same size as a memory line (the unit of compression). Upon a cache miss, the cache requests the corresponding line from memory, by providing real address 270 that caused the miss. The real address is divided into two parts: the log2(line length) least significant bits which are the offset of the address within the line, where log2( ) is the logarithm in base 2, and the remaining bits which are used as an index in the directory 220, which contains a line entry for each line in the supported real address range. In FIG. 2, address A1 (271) corresponds to line entry 1 (221), address A2 (272) corresponds to line entry 2 (222), address A3 (273) corresponds to line entry 3 (513) and address A4 (274) corresponds to line entry 4 (514). Different addresses are used in the example to show different ways of storing compressed data in the compressed main memory. In this example, the line having address A1 compresses very well (for example, a line consisting of all zeros). Such a line is stored entirely in the CTT entry 221, and does not require memory sectors. The line at address A2 compresses less well, and requires two memory sectors 231 and 232, which are stored in the data section 230. Line entry 222 contains pointers to the memory sectors 231 and 232. Note that the last part of memory sector 232 is unutilized. The line having address A3 requires 3 memory sectors, 233, 234 and 235. The space left unutilized in sector 235 is large enough to store part of the compressed line having real address A4, which in turn uses sector 236 and part of 235. The lines at addresses A4 and A3 are called roommates.
Compressor 261 is used when dirty lines in the cache are written back into memory. Upon a cache writeback, a dirty line is compressed. If it fits in the same amount of memory it used before the writeback, it is stored in place. Otherwise, it is written in the appropriate number of sectors. If the number of required sectors decreases, the unused sectors are added to a free-sector list. If the number of required sectors increases, they are retrieved from the free-sector list.
FIG. 3 shows possible organizations of the entries in the directory or CTT 220. Three different line organizations are illustrated. Entry 1 (306) contains a set of flags (301), and the addresses of 4sectors. If the line size is 1024 bytes, and the memory sector size is 256, the line requires at most 4 sectors. Entry 2 (307) contains a set of flags, the address of the first sector used by the line, the beginning of the compressed line, and the address of the last sector used by the line. If the line requires more than 2 memory sectors, the sectors are connected by a linked list of pointers (namely, each memory sector contains the address of the subsequent one). Entry 3 contains a set of flags, and a highly compressed line, which compresses to 120 bits or less. The flags in the example can be flag 302 indicating whether the line is stored in compressed format or uncompressed; flag 303 indicating if the line is highly compressible and is stored entirely in the directory entry; flag 304 (2 bits) indicating how many sectors the line uses; and flag 305 (4 bits) containing the fragment information, namely what portion of the last used sector is occupied by the line (this information is used for roommating). The maximum compression ratio achievable in a system with memory compression that relies on the above-described compressed-memory organization depends on the size of the directory, i.e., the maximum number of real addresses is equal to the number of directory entries in the directory.
In a related field, methods for partitioning an uncompressed memory are taught, for example, by R. R. Guyette, et al., in U.S. Pat. No. 4,564,903 entitled “Partitioned multiprocessor programming system”. This patent teaches a control method for a multiprocessor (MP) system having plural CPUs sharing a main storage (MS) and I/O processing means for connecting a plurality of I/O devices to MS, the control method enabling the MP to execute a uniprocessor programming system (UPS) simultaneously on plural CPUs in the MP, even though the UPS is designed to only execute on a uniprocessor (UP) system having the same or a different architecture than the MP. This patent teaches apparatus and methods for a non-compressed memory contained within the MP system. However, it does not teach apparatus and methods for a compressed memory system that is not part of the MP system, nor for a compressed memory that is shared by different computer systems and that is not part of any of the computer systems.
Partitioning is also taught, for example, in U.S. Pat. No. 4,843,541 entitled “Logical resource partitioning of a data processing system” issued to G. H. Bean, et al. on Jun. 27, 1989. This patent teaches a method of restricting guest operations in a data processing system to system resources assigned to a guest, the resources in the system including one or more real CPUs, a system main storage (MS), an optional system extended storage (ES), and a plurality of I/O channels using I/O processors for connecting to the system a plurality of I/O device control units with their I/O devices, a host hypervisor (host) which includes software, the host supervising plural software control programs (guests) capable of concurrently and independently operating in the system and the guests may be the same or different types of control programs, subchannels (SCHs) for representing I/O devices to the host and to the guests, each guest being restricted to using an assigned subset (partition) of system resources. However, the patent does not teach sharing a network-attached compressed memory among different hosts.
Partitioning as taught in the art comprises methods for translating real addresses as seen by software components running on a computer into real addresses as managed by the computer. These software components can be multiple images of the same operating system, or of different operating systems, and therefore they can perform logical-to-real address translation. Partitioning treats the real addresses produced by these software components as logical addresses, and performs a further logical-to-real translation. If the hardware does not support memory compression, real addresses are equivalent to physical addresses. However, if the memory is compressed, real addresses are not equivalent to physical addresses, and a further translation is necessary. Conventional partitioning also includes protection mechanisms that prevent software components running in a specific partition from accessing the content of memory of software components running in the other partitions.
However, partitioning as taught in the art does not address how to provide sharing of memory resources, as well as security mechanisms, within devices that are physically separate from the computer systems where the software component using the data are executed, so that the sharing and security mechanisms are not controlled by the computer systems, and are in fact transparent to such computer systems.